class Solution {
public:

    int dfs(int n, vector<int>& mem){
        if(n == 0) return 1;
        else if(n<0) return 0;

        if(mem[n] != -1){
            mem[n] = dfs(n-1, mem) + dfs(n-2, mem);
        }
        return mem[n];
    }

    int climbStairs(int n) {

        vector<int> mem(n, -1);
        dfs(n, mem);

        return mem[0];
    }
};